#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2021-01-19 9:30 上午
# @Author  : yangdy
# @File    : 2021-01-19.1584.连接所有点的最小费用
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        ans, c, n = 0, 0, len(points)
        ss = [True for i in range(len(points))]
        dist = [-1 for i in range(len(points))]
        dist[0] = 0

        def cal_dist(i, j):
            return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])

        while c < n:
            m, mi = 0, -1
            for i in range(n):
                if ss[i]:
                    if dist[i] != -1 and (mi == -1 or dist[i] < m):
                        m, mi = dist[i], i
            ans, c, ss[mi] = ans + m, c + 1, False
            for i in range(n):
                if ss[i]:
                    mm = cal_dist(mi, i)
                    if dist[i] == -1 or dist[i] > mm:
                        dist[i] = mm
        return ans


